#!/usr/env/bin python
# -*- coding: utf-8 -*-
# filename: 二叉搜索树迭代器.py
# creator: yangdy
# create date: 2018/3/26
"""  
二叉搜索树迭代器
TODO模块说明
Public Class:
-	TODO类名: TODO类说明 
Public Methods: 
-	TODO方法名: TODO方法说明
"""


# Definition for a  binary tree node
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self._root = root
        l = []

        def work(p):
            if not p:
                return
            if p.left:
                work(p.left)
            l.append(p.val)
            if p.right:
                work(p.right)
        work(root)
        self._l = l
        self._ll = len(l)
        self._i = 0
        print(l)

    def hasNext(self):
        """
        :rtype: bool
        """
        return self._i < self._ll

    def next(self):
        """
        :rtype: int
        """
        ans = self._l[self._i]
        self._i += 1
        return ans

def main():
    # Your BSTIterator will be called like this:
    root = TreeNode(1)
    i, v = BSTIterator(root), []
    while i.hasNext(): v.append(i.next())
    print(v)

if __name__=='__main__':
    main()